APUNTES MATEMATICA DISCRETA

Unidad 1: Logica

Tablas

Operaciones Logicas

AND OR NOT COND. BICOND.
pp qq pqp \land q
V V V
V F F
F V F
F F F
pp qq pqp \lor q
V V V
V F V
F V V
F F F
pp ¬p\neg p
V F
F V
pp qq pqp \rArr q
V V V
V F F
F V V
F F V
pp qq pqp \Leftrightarrow q
V V V
V F F
F V F
F F V

Presedencia de Operadores

1 ¬\neg
2 \land
3 \lor
4 \rArr
5 \Leftrightarrow

Tabla de Leyes Logicas

# Nombre Propiedad
1 Involucion ¬(¬p)p\neg(\neg p) \equiv p
2 Conmutatividad pqqppqqpp \land q \equiv q \land p   p \lor q \equiv q \lor p
3 Asociatividad p(qr)(pq)rp(qr)(pq)rp \land (q \land r) \equiv (p \land q) \land r   p \lor (q \lor r) \equiv (p \lor q) \lor r
4 Distributividad p(qr)(pq)(pr)p(qr)(pq)(pr)p \land (q \lor r) \equiv (p \land q) \lor (p \land r) \\ p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)
5 Idempotencia ppppppp \land p \equiv p   p \lor p \equiv p
6 De Morgan ¬(pq)¬p¬q¬(pq)¬p¬q\neg (p \land q) \equiv \neg p \lor \neg q   \neg(p \lor q) \equiv \neg p \land \neg q
7 Absorcion p(pq)pp(pq)pp \land (p \lor q) \equiv p   p \lor (p \land q) \equiv p
8 Identidad pVppFpp \land V \equiv p   p \lor F \equiv p
9 Dominacion pVVpFFp \lor V \equiv V   p \land F \equiv F
10 Bicondicional pq(pq)(qp)p \Leftrightarrow q \equiv (p \rArr q) \land (q \rArr p)
11 Condicional pq¬pqp \rArr q \equiv \neg p \lor q
12 Tercero Excluido p¬pVp \lor \neg p \equiv V
13 Simplificacion pqpVp \land q \rArr p \equiv V
14 Adicion ppqVp \rArr p \lor q \equiv V

Nota: Cuando nos presentan un razonamiento hay dos tipos de razonamientos categoricos y no categoricos. En los categoricos las premisas tienen cuantificadores (x:,x:)(\forall x: , \exist x:) y por lo tanto definir un conjunto universal e.g: U={x/x es un auto”}U=\{x/\text{``} x \text{ es un auto''}\}, las premisas son funciones e.g: p(x)=x es verde”p(x) = \text{``}x \text{ es verde''}, por ultimo, en el caso de que un razonamiento categorico sea invalido la forma de justificar que es invalido es definiendo un conjuto que demuestre la contradiccion del argumento.

Caso contrario son los no categoricos, en este caso las premisas no tienen cuantificadores, tampoco hay que definir un conjunto universal.

Reglas de Inferencia

Nombre Condiciones
Modus Ponens "M.P." AB;ABA \rArr B ; A   \therefore B
Modus Tolens "M.T." AB;¬BAA \rArr B ; \neg B   \therefore A
Silogismo Hipotetico "S.H." AB;BCACA \rArr B ; B \rArr C   \therefore A \rArr C
Silogismo Disyuntivo "S.D." AB;¬ABA \lor B ; \neg A   \therefore B
Ley de Combinacion "L.C." A;BABA ; B   \therefore A \land B

Reglas de Inferecia Razonamientos Categoricos (CON CUANTIFICADORES):

Nombre Condiciones
Particularizacion Universal "P.U." x:p(x)p(a)\forall x: p(x) \therefore p(a)
Generalizacion Universal "G.U." p(a)x:p(x)(Solo se cumple si “a" es generico)p(a) \therefore \forall x: p(x) \text{(Solo se cumple si ``a" es generico)}
Particularizacion Existencial "P.E." x:p(x)p(a)\exists x: p(x) \therefore p(a)
Generalizacion Existencial "G.E." p(a)x:p(x)p(a) \therefore \exists x: p(x)

pq{¬q¬pp\rArr q\begin{cases} \neg q\rArr\neg p\\ \end{cases}

Unidad 2.1: Conjuntos

Propiedades de la inclusion

XYa:aXaYX \subseteq Y \Leftrightarrow \forall a: a \in X \rArr a \in Y

  1. A:AA. Todo conjunto esta incluido en si mismo.\forall A: A \subseteq A. \text{ Todo conjunto esta incluido en si mismo.}
  2. A:A. El vacio esta incluido en todo conjuto.\forall A: \empty \subseteq A. \text{ El vacio esta incluido en todo conjuto.}
  3. A:AU. Todo conjunto esta includo en el Universal.\forall A: A \subseteq U. \text{ Todo conjunto esta includo en el Universal.}
  4. A,B,C:ABBCAC. Propiedad Transitiva.\forall A, B, C: A \subseteq B \land B \subseteq C \rArr A \subseteq C. \text{ Propiedad Transitiva.}

Operaciones entre conjuntos

Operacion Formula
Union AB=x/xAxBA \cup B = { x/ x \in A \lor x \in B }
Interseccion AB=x/xAxBA \cap B = { x/ x \in A \land x \in B }
Diferencia AB=A¬B=x/xAxBA - B = A \cap \neg B ={ x/ x \in A \land x \notin B }
Complemento ¬A=UA\neg A = U - A
Diferencia Simetrica AΔB=x/xAxBA \Delta B = { x/ x \in A \veebar x \in B }

Propiedades de las Operaciones

# Nombre Propiedad
1 Involucion ¬(¬A)=A\neg(\neg A) = A
2 Conmutativida AB=BAAB=BAA \cup B = B \cup A \\ A \cap B = B \cap A
3 Asociatividad A(BC)=(AB)CA(BC)=(AB)CA\cup (B\cup C) = (A\cup B)\cup C \\ A \cap (B\cap C) = (A \cap B) \cap C
4 Distributividad A(BC)=(AB)(AC)A(BC)=(AB)(AC)A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \\ A \cap (B \cup C) = (A \cap B) \cup (A \cap C)
5 Idempotencia AA=AAA=AA \cup A = A   A \cap A = A
6 Leyes de Morgan ¬(AB)=¬A¬B¬(AB)=¬A¬B\neg(A \cap B) = \neg A \cup \neg B   \neg(A \cup B) = \neg A \cap \neg B
7 Neutro AU=AA=AA \cap U = A   A \cup \empty = A
8 Absorbente A=AU=UA \cap \empty = \empty   A \cup U = U
9 Absorcion A(AB)=AA(AB)=AA \cap (A \cup B) = A   A \cup (A \cap B) = A
10 Equivalencia de la Diferencia AB=A¬BA - B = A \cap \neg B
11 Complementacion A¬A=A¬A=UA \cap \neg A = \empty   A \cup \neg A = U

hola\phantom{hola}

Conjunto de Partes

P(A)=X/XAP(A) = {X/ X \subseteq A}

XP(A)XAX \in P(A) \Leftrightarrow X \subseteq A

ACLARACIONES:

Particion de un conjunto

continuara?...

Producto Cartesiano

Propiedades del producto cartesiano

# Propiedad
1 A×=×A=A \times \empty = \empty \times A = \empty
2 A×BB×A \times B \neq B \times
3 A×(B×C)(A×B)×AA \times (B \times C) \neq (A \times B) \times A
4 (AB)×C=(A×C)(B×C)(AB)×C=(A×C)(B×C)(A \cap B) \times C = (A \times C) \cap (B \times C) \\ (A \cup B) \times C = (A \times C) \cup (B \times C)

Demostraciones

En un caso de demostracion se compone de la siguiente manera, se tiene una o varias hipotesis y una sola tesis, LAS HIPOTESIS SE CONSIDERAN CIERTAS, y es gracias a esto que vamos a poder reemplazar alguna expresion de la tesis por una de la hipotesis

Caso particular: Si tengo que demostrar una igualdad ( == ) debo hacer la demostracion en ambos sentidos, es decir, partir desde el miembro izquierdo, desarrollar hasta llegar al derecho y viceversa. EN ALGUNOS CASOS, las propiedades se pueden aplicar en ambos sentidos, pero esto no siempre se cumple, para esos casos solo queda volver a empezar el desarrollo desde cero.

Demostraciones con Partes de Conjuntos

Cuando se tiene que demostrar algo que involucre partes de un conjunto, se trabaja de la misma manera que con conjuntos, solo que ahora los elementos de P(AA) (siendo AA un conjunto o subconjunto generico) van a ser otros conjuntos. Esto es poruqe P(A)P(A) nos devuelve otro conjunto... pero de mas conjuntos.

En vez de representar un elemento del conjunto como x:xA\forall x: x \in A sera de esta forma X:XA\forall X: X \in A. Notese la diferencia que ahora el elemento generico del conjunto es otro conjunto.

Ademas, a la hora de reemplazar partes de un conjunto, se habla de un conjunto generico que esta incluido en este supuesto conjunto.

E.g: P(A)X:XP(A)XAP(A) \rArr \forall X: X \in P(A) \rArr X \subseteq A

El resto de la demostracion deberia ser identica que con conjuntos.

Unidad 2.2: Induccion

PIC (Principio de Induccion Completa)

  1. v[p(1)]=Vv[ p(1) ] = V   Paso base.
  2. v[p(h)]=Vv[p(h+1)]=Vv[ p(h) ] = V \rArr v[ p(h+1) ] = V   Paso inductivo.

Aclaraciones:

Herramientas

Pares e Impares

Suma Multiplicacion
++ Par Impar
Par Par Impar
Impar Impar Par
×\times Par Impar
Par Par Par
Impar Par Impar

hola\phantom{hola}

hola\phantom{hola}

hola\phantom{hola}

Binomio de Newton

(ab)0=1(ab)1=ab(ab)2=a22ab+b2(ab)3=a33a2b+3ab2b3(ab)4=a44a3b+6a2b24ab3+b4(ab)5=a55a4b+10a3b210a2b3+5ab4+b5\begin{aligned} (a-b)^0 &= 1 \\ (a-b)^1 &= a-b \\ (a-b)^2 &= a^2 - 2ab + b^2 \\ (a-b)^3 &= a^3 - 3a^2b + 3ab^2 - b^3 \\ (a-b)^4 &= a^4 - 4a^3b + 6a^2b^2 - 4ab^3 + b^4 \\ (a-b)^5 &= a^5 - 5a^4b + 10a^3b^2 - 10a^2b^3 + 5ab^4 + b^5 \end{aligned}

Binomio de simplificado (h+1)

(h+1)0=1(h+1)1=h1+1(h+1)2=h2+2h+1(h+1)3=h3+3h2+3h+1(h+1)4=h4+4h3+6h2+4h+1(h+1)5=h5+5h4+10h3+10h2+4h+1\begin{aligned} (h+1)^0 &= 1 \\ (h+1)^1 &= h^1+1 \\ (h+1)^2 &= h^2 + 2h + 1 \\ (h+1)^3 &= h^3 + 3h^2 + 3h + 1 \\ (h+1)^4 &= h^4 + 4h^3 + 6h^2 + 4h + 1 \\ (h+1)^5 &= h^5 + 5h^4 + 10h^3 + 10h^2 + 4h + 1 \end{aligned}

Numeros Primos

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Algunas recomendaciones

hola\phantom{hola}

hola\phantom{hola}

hola\phantom{hola} hola\phantom{hola}

Unidad 3: Divisibilidad

Division entera

Partes de la division

Dados dos numeros DD y dd, con d0d\neq0, existen y son unicos otros dos enteros cc y rr tales que: D=cd+rD=c\cdot d+r y 0rd0\le r \le \lvert d\rvert

Si d>0d>0:

c=ent(Dd)r=mant(Dd)dc =\text{ent} \left(\frac{D}{d}\right) \land r = \text{mant} \left(\frac{D}{d}\right)\cdot d

Si d<0d<0:

d=dc=ent(Dd)r=mant(Dd)d^\prime = -d \rArr c^\prime = \text{ent}\left(\frac{D}{d^\prime}\right) \land r^\prime = \text{mant}\left( \frac{D}{d^\prime} \right)

Luego:

c=cr=rc = c^\prime \land r = r^\prime

Relacion de Divisibilidad

Sean: a,bZ:a,b \in \Z:

ab    kZ/b=ka a\vert b \iff \exist k \in \Z / b = k \cdot a

hola\phantom{hola}

hola\phantom{hola}

Propiedades

  1. aZ:aa\forall a \in \Z: a\vert a

    Dem:

    aZ:a=a11Zaa\forall a \in \Z: a=a\cdot 1 \land 1\in\Z \rArr a\vert a

  2. a,b,cZ:abbcac\forall a,b,c \in \Z: a\vert b \land b\vert c \rArr a\vert c

    Dem:

    a,b,cZ:abbc(1)b=akc=btc=(ak)tc=a(kt)ac\forall a,b,c \in \Z: a\vert b \land b\vert c \rArr ^{(1)} b=a\cdot k \land c=b\cdot t\rArr c = (a\cdot k) \cdot t\rArr c=a\cdot (k\cdot t) \rArr a\vert c

    (1):k,tZ(1): k,t \in \Z

  3. a,b,cZ:abaca(b+c)\forall a,b,c \in \Z: a\vert b \land a\vert c \rArr a\vert (b+c)

    Dem:

    a,b,cZ:abacb=akc=aqb+c=ak+aqb+c=a(k+q)a(b+c)\forall a,b,c \in \Z: a\vert b \land a\vert c \rArr b =a\cdot k \land c=a\cdot q \\ \rArr b+c = a\cdot k + a\cdot q\rArr b+c = a\cdot (k+q)\rArr a\vert (b+c)

  4. a,b,cZ:aba(bc)\forall a,b,c \in \Z: a\vert b \rArr a\vert (b\cdot c)

    Dem:

    a,b,cZ:b=akbc=(ak)cbc=a(kc)a(bc)\forall a,b,c \in \Z: b=a\cdot k \rArr b\cdot c = (a\cdot k)\cdot c\rArr b\cdot c = a\cdot(k\cdot c)\rArr a\vert (b\cdot c)

Numeros Primos

Teorema Fundamental de la Aritmetica

n=p1k1p2k2prkr n=p_1^{k_1}\cdot p_2^{k_2}\cdot \ldots \cdot p_r^{k_r}

Esto es la wea de factorear...

Minimo comun Multiplo (M.C.M)

hola\phantom{hola}

hola\phantom{hola}

Maximo comun Divisor (M.C.D)

Algoritmmo de Euclides

El algoritmo de euclides se usa para calcular el maximo comun divisor (mcd) entre dos numeros, pero ademas se utiliza para expresarlos como combinacion lineal.

Propiedad:

Dados dos enteros aa y bb, el mcd(a,b)=mcd(b,r)\text{mcd}(a,b) = \text{mcd}(b,r) siendo rr el resto de la division de aa por bb.

Demostrar: Da,bDb,rxDa,bxaxbxbq+rxbxbxbq+rxb(q)xbxbq+r+b(q)xbxrxbxDb,r \text{Demostrar: } D_{a,b} \subseteq D_{b,r} \\ \forall x \in D_{a,b} \rArr x\vert a \land x\vert b \rArr x\vert b\cdot q+r \land x\vert b \land x\vert b \\ \rArr x\vert b\cdot q+r \land x\vert b\cdot(-q) \land x\vert b \\ x\vert b\cdot q + r + b\cdot (-q) \land x\vert b \\ x\vert r \land x\vert b \rArr x\in D_{b,r}

Algoritmo de Euclides de Forma Matricial

Siendo: mcd(a,b)=nmcd(a,b) = n

n=k1a+k2bn = k_1 \cdot a + k_2 \cdot b

Ej: Calcular mcd (720,224)(720,224)

hola\phantom{hola}

hola\phantom{hola}

hola\phantom{hola}

hola\phantom{hola}

hola\phantom{hola}

# k1k_1 k2k_2 nn Operacion de Filas
1 11 00 720720 F1F_1
2 00 11 224224 F2F_2
3 11 3-3 4848 F3=F13F2F_3 = F_1 - 3\cdot F_2
4 4-4 1313 3232 F4=F24F3F_4 = F_2 - 4\cdot F_3
5 55 16-16 1616 F5=F3F4F_5 = F_3 - F_4
6 00 F6=F42F5F_6 = F_4 - 2\cdot F_5

Ahora tomo la anteultima fila, en ella estaran los valores que necesito:

mcd$(720,224) = 16$

16=5720+(16)22416 = 5\cdot 720 + (-16)\cdot 224

A la hora de completar la matriz trabajar siempre con valores positivos para evitar errores, pero si se cambia de signo algun numero recordar cambiarle el signo tambien al numero que multiplique a dicho numero que se cambio el signo.

Teorema de Bezout

Dados dos enteros aa y bb:

mcd(a,b)=1    1=sa+tb con s,tZ \text{mcd}(a,b) = 1 \iff 1 = s\cdot a + t\cdot b \text{ con } s,t\in\Z

Esto solo sucede si y solo si el mcd$(a,b) = 1$.

Algunas recomendaciones

Unidad 4: Relaciones

Definiciones

Dados dos conjuntos AA y BB, llamamos relacion de AA en BB a cualquier subconjunto de A×BA\times B

R:ABR:A\to B RR es una relacion de AA en BB. (RA×B)(R\sube A\times B) es cualquier subconjunto incluido en el producto cartesiano.

Operaciones entre Matrices

  1. Suma Logica o Disyuncion (\lor):

    AB=CA\lor B = C Donde A{0,1}n×m,B{0,1}n×m,C{0,1}n×mA\in\{0,1\}^{n\times m}, B\in\{0,1\}^{n\times m}, C\in\{0,1\}^{n\times m}.

    i:1n:j:1m:cij=aijbij\forall i: 1\ldots n: \forall j: 1\ldots m: c_{ij} =a_{ij} \lor b_{ij}

  2. Producto Logico o Conjunsion (\land):

    AB=CA\land B = C Donde A{0,1}n×m,B{0,1}n×m,C{0,1}n×mA\in\{0,1\}^{n\times m}, B\in\{0,1\}^{n\times m}, C\in\{0,1\}^{n\times m}.

    i:1n:j:1m:cij=aijbij\forall i: 1\ldots n: \forall j: 1\ldots m: c_{ij} =a_{ij} \land b_{ij}

  3. Producto Matricial Booleano (\bullet):

    AB=CA\cdot B = C Donde A{0,1}n×m,B{0,1}m×p,C{0,1}n×pA\in\{0,1\}^{n\times m}, B\in\{0,1\}^{m\times p}, C\in\{0,1\}^{n\times p}.

    At=BA^t = B Donde A{0,1}n×m,B{0,1}n×mA\in\{0,1\}^{n\times m}, B\in\{0,1\}^{n\times m}.

    i:1n:j:1m:bij=aji\forall i: 1\ldots n: \forall j: 1\ldots m: b_{ij} =a_{ji}

  4. Complemento de una matriz:

    Aˉ=B\bar{A} = B Donde A{0,1}n×m,B{0,1}n×mA\in\{0,1\}^{n\times m}, B\in\{0,1\}^{n\times m}.

    i:1n:j:1m:bij=¬aij\forall i: 1\ldots n: \forall j: 1\ldots m: b_{ij} = \neg{a_{ij}}

Propiedades de Matrices

# Nombre Propiedad
1 Idempotencia AA=AA\lor A = A, AA=AA\land A = A
2 Conmutatividad AB=BAAB=BAA\lor B = B\lor A \\ A\land B = B\land A
3 Asociatividad A(BC)=(AB)CA(BC)=(AB)CA(BC)=(AB)CA\lor (B\lor C) = (A\lor B) \lor C \\ A\land (B\land C) = (A\land B) \land C \\ A\cdot (B\cdot C) = (A\cdot B) \cdot C
4 Asociatividad AA=AA\lor A = A, AA=AA\land A = A
5 Distributividad A(BC)=(AB)(AC)A(BC)=(AB)(AC)A\lor (B\land C) = (A\lor B)\land (A\lor C) \\ A\land (B\lor C) = (A\land B)\lor (A\land C)

Comparacion de Matrices

Sean A,B{0,1}n×mA,B\in \{ 0,1\}^{n\times m}

A<Baij<biji,jA<B \Leftrightarrow a_{ij}<b_{ij} \forall i, \forall j

ABaijbiji,jA\leq B \Leftrightarrow a_{ij}\leq b_{ij} \forall i, \forall j

Matriz de una Relacion

Sea R:ABR:A\to B con A={a1,a2,,an} y B={b1,b2,,bn}A=\{ a_1,a_2,\ldots,a_n \} \text{ y } B=\{ b_1,b_2,\ldots,b_n \}

MR{0,1}n×m{1 si (ai,bj)R0 si (ai,bj)R M_R \in \{0,1\}^{n\times m} \begin{cases} 1 & \text{ si }(a_i,b_j)\in R \\ 0 & \text{ si }(a_i,b_j)\notin R \end{cases}

Operaciones con Matrices

Sean R:ABR:A\to B y S:ABS:A\to B

Sea MRM_R la matriz de RR y MSM_S la matriz de SS

MRS=MRMSMRS=MRMSMR1=(MR)tMR=(MR)M_{R \cup S} = M_R \lor M_S \\ M_{R \cap S} = M_R \land M_S \\ M_R^{-1}= (M_R)^t \\ M_{\overline{R}} = \overline{(M_R)}

Composicion de Relaciones

Dadas R:ABR:A\to B y S:BCS:B\to C

SR={(x,z)A×C/yB(x,y)R(y,z)S} S\circ R=\{(x,z)\in A\times C/ \exist y\in B \land (x,y)\in R \land (y,z)\in S \}

Para hacer composicion de matrices hay que hacer el producto matricial entre las matrices, el resultado sera la matriz de la relacion compuesta. Se tiene que respetar el orden.

MSR=MRMSM_{S\circ R}= M_R \cdot M_S

Relaciones Binarias

Son todas las relaciones que conjunto de partida es igual al de llegada R:AAR:A\to A.

Ej: R:AA tal que R={(x,y)A×A/y=x2}R:A\to A \text{ tal que }R=\{ (x,y) \in A\times A/y=x^2 \}

hola\phantom{hola}

hola\phantom{hola}

hola\phantom{hola}

hola\phantom{hola}

hola\phantom{hola}

hola\phantom{hola}

hola\phantom{hola}

hola\phantom{hola}

hola\phantom{hola}

Propiedades de las Relaciones

Sea una relacion binaria R:AA:R:A\to A:

Orden de evaluacion

  1. Es reflexiva?
  2. Es a-reflexiva?
  3. Es simetrica?
  4. Es a-simetrica?
  5. Es antisimetrica?
  6. Es transitiva?

Nota: Cuando son elementos finitos lo mejor es realizar la matriz, pero cuando son elementos infinitos tendremos que recurrir a la defincion.

Relacion de Conectividad

Sea R:AA\text{Sea } R:A\to A            R2=RRR^2 = R\circ R

En R:xyz\text{En }R:x\to y\to z      En R2=xz\text{En }R^2 = x\to z

En otras palabras la matris de R2R^2 nos devuelve todas las relaciones cuyos caminos son de longitud 22. Esto tambien sucede para cualquier potencia nn, nos devuelve todos los caminos de longitud nn.

xRnyexite un camino de longitud n entre x e yxR^ny\Leftrightarrow \text{exite un camino de longitud } n \text{ entre } x \text{ e } y

Relacion de Equivalencia

R:AA es de quivalencia si es{ReflexivaSimetricaTransitivaR:A\to A \text{ es de quivalencia si es} \begin{cases} \text{Reflexiva} \\ \text{Simetrica}\\ \text{Transitiva} \end{cases}

A las relaciones de quivalencia se las suele representar por el simbolo ~

Clase de Equivalencia

Sea (A;~)a=[a]=Cl(a)={xA/x~a} \text{Sea } (A;\text{\textasciitilde{}}) \text{\quad} \overline{a} = [a] = Cl(a)=\{ x\in A/ x \text{\textasciitilde{}}a \}

Conjunto de Clases

Sea (A;~)A/~={Cl(a)/aA} \text{Sea } (A;\text{\textasciitilde{}}) \text{\quad} A/\text{\textasciitilde{}} = \{ Cl(a)/ a\in A \}

Propiedades de las Clases de Equivalencia

Aclaracion 1: Las siguientes propiedades son validas porque se parte de que es una relacion de equivalencia, es decir, ya esta demostrado que la relacion es de equivalencia.

Aclaracion 2: Es lo mismo decir Cl(a)Cl(a) que [a][a]

Consideremos RR relacion de equivalencia definida en un conjunto AA

Teorema Fundamental de las Relaciones de Equivalencia

Toda relacion de equivalencia definida en un conjunto, provoca en el mismo una particion (conjunto cociente)"

Reciprocamente, toda particion de un conjunto induce en el mismo una relacion de equivalecia.

Relacion de Equivalencia    Particion del conjunto\text{Relacion de Equivalencia} \iff \text{Particion del conjunto}

Basicamente cada relacion de equivalencia me determina una particion del conjunto (recordar definicion de particion). Y si hay una particion dentro del conjunto es porque hay una relacion de equivalencia que lo determina.

Demostracion del teorema

Toda relacion de equivalencia definida en un conjunto, provoca en el mismo una particion (conjunto cociente)"

Propiedades que debe cumplir:

  1. Cl(x)Cl(x) \neq \varnothing
  2. Cl(x)Cl(y)=(si Cl(x)Cl(y))Cl(x) \cap Cl(y) = \varnothing \quad (\text{si }Cl(x)\neq Cl(y))
  3. Cl(x)=A\cup Cl(x) = A

Dem: xA:xCl(x) por reflexividadxCl(x)\forall x\in A:x\in Cl(x) \text{ por reflexividad} \rArr x\in\cup Cl(x)

Reciprocamente, toda particion de un conjunto induce en el mismo una relacion de equivalecia.

Por hipotesis P={A1,A2,A3,,An}P=\{ A_1,A_2,A_3,\ldots,A_n \} es una particion de A.

Deinimos en A:xRyAiP:xAiyAj)A: xRy \Leftrightarrow\exist A_i \in P:x\in A_i\land y\in A_j )

  1. Reflexiva: xA:xAi(3ra cond de particion)idempot.xAixAixRx\forall x\in A: x\in A_i (3^\text{ra}\text{ cond de particion})\\\rArr^{\text{idempot.}}x\in A_i\land x\in A_i\rArr xRx

  2. Simetrica: x,yA:xRyAiP:xAiyAiconmutativ.AiP:yAixAiyRx\forall x,y\in A: xRy\rArr\exist A_i\in P: x\in A_i\land y\in A_i\\\rArr^{\text{conmutativ.}} \exist A_i\in P: y\in A_i\land x\in A_i\rArr yRx

  3. Transitiva: x,y,zA:xRyyRz[AiP:xAiyAi][AkP:yAkzAk]Ai=Ak(2da prop de particion)AiP:xAizAixRz\forall x,y,z\in A: xRy\land yRz\\\rArr [\exist A_i\in P:x\in A_i\land y\in A_i]\land[\exist A_k\in P:y\in A_k\land z\in A_k]\\\rArr A_i = A_k (2^\text{da}\text{ prop de particion})\\\rArr\exist A_i\in P: x\in A_i\land z\in A_i\rArr xRz

Aclaraciones:

Unidad 5: Relaciones de Orden

R:AA es de orden{ReflexivaAntisimetricaTransitivaR: A\to A \text{ es de } \textbf{orden}\begin{cases} \text{Reflexiva}\\ \text{Antisimetrica}\\ \text{Transitiva}\\ \end{cases}

Las relaciones de orden tambien se llaman de orden amplio

Diagrama de Hasse

Si se sabe que una relacion es de orden entonces se puede armar un Diagrama de Hasse. Un diagrama de hasse es un digrago de relaciones simplificado, sin bucles ni relaciones transitivas. Solo aristas directas.

Tambien se puede omitir las flechas pero para eso se tiene que hacer de forma vertical, siendo los elementos inferiores los que estan incluidos en en los elementos superiores.

Conjunto Totalmente Ordenado (TTO)

A esta TTO    x,yA:(xyyx)\text{A esta TTO}\iff\forall x,y\in A: (x\preceq y \lor y\preceq x)

Orden Reciproco

Sea (A;)Sea R:AA/xRyyx\text{Sea }(A;\preceq)\quad\text{Sea } R:A\to A/ xRy\Leftrightarrow y\preceq x

Orden usual del Producto

Sean (A;1) y (B;2)\text{Sean }(A;\preceq_1)\text{ y }(B;\preceq_2)

(x;y)R(z;t)x1zy2t(x;y)R(z;t)\Leftrightarrow x\preceq_1z \land y\preceq_2 t

Elementos Notables de un Conjunto Ordenado

Maxiamal

Sea (A;)\text{Sea }(A;\preceq)

mA es maximal de AxA:mxx=mm\in A \text{ es }\textbf{maximal}\text{ de } A \Leftrightarrow\forall x\in A: m\preceq x\rArr x = m

Minimal

Sea (A;)\text{Sea }(A;\preceq)

mA es minimal de AxA:xmx=mm\in A \text{ es }\textbf{minimal}\text{ de } A \Leftrightarrow\forall x\in A: x\preceq m\rArr x = m

Atomo

Sea (A;) un conjunto ordenado con primer elemento p\text{Sea }(A;\preceq)\text{ un conjunto ordenado con primer elemento } p

mA es atomo de AxA:(xmx=mx=p)m \in A \text{ es }\textbf{atomo}\text{ de } A \Leftrightarrow\forall x\in A: (x\preceq m \rArr x=m \lor x=p)

Conjunto Bien Ordenado

Sea (A;)\text{Sea }(A;\preceq)

A esta Bien Ordenado todo subconjunto de A tiene 1er elementoA \text{ esta Bien Ordenado } \Leftrightarrow \text{todo subconjunto de } A \text{ tiene } 1^{er}\text{ elemento}

Cotas Superiores e Inferiores

Sea (A;) un conjunto ordenado y BA\text{Sea } (A;\preceq)\text{ un conjunto ordenado y } \varnothing \neq B\sube A

sA es cota superior de BxB:xss\in A \text{ es } \textbf{cota superior} \text{ de } B \Leftrightarrow\forall x\in B:x\preceq s

Sea (A;) un conjunto ordenado y BA\text{Sea } (A;\preceq)\text{ un conjunto ordenado y } \varnothing \neq B\sube A

iA es cota inferior de BxB:ixi\in A \text{ es } \textbf{cota inferior} \text{ de } B \Leftrightarrow\forall x\in B:i\preceq x

Redes

Sea (A;) un conjunto ordenado.\text{Sea } (A;\preceq) \text{ un conjunto ordenado.}

Es Superior Semirreticulo    a,bA: supremo(a,b)\text{Es }\textbf{Superior Semirreticulo} \iff \forall a,b \in A: \exist \text{ supremo}(a,b)

Sea (A;) un conjunto ordenado.\text{Sea } (A;\preceq) \text{ un conjunto ordenado.}

Es Inferior Semirreticulo    a,bA: infimo(a,b)\text{Es }\textbf{Inferior Semirreticulo} \iff \forall a,b \in A: \exist \text{ infimo}(a,b)

Sea (A;) un conjunto ordenado.\text{Sea } (A;\preceq) \text{ un conjunto ordenado.}

(A;) es Red    es superior e iferior semirreticulo(A;\preceq) \text{ es} \textbf{ Red} \iff \text{es superior e iferior semirreticulo}

Entre todo par de elementos debe existir supremo e infimo.

Entonces para que una relacion sea red, tiene que existir un supremo e infimo para cualquier par de elementos. En relacion a esto entonces, para verificar que esto se cumpla lo mas eficiente seria verificar si hay supremo e infimo entre los elementos incomparables, si es que tienen supremo e infimo en comun entonces la relacion es una red.

Propiedades

Si absup(a,b)=byinf(a,b)=a\text{Si } a\preceq b \rArr \text{sup}(a,b) = b \quad y \quad \text{inf}(a,b) =a

Tabla

Propiedades para las operaciones de supremo e infimo:

Sea (A;) una red. Las operaciones  e  cumplen:\text{Sea } (A;\preceq) \text{ una red. Las operaciones }\vee\text{ e }\land\text{ cumplen:}

# Nombre Propiedad
1 Operacion Cerrada x,yA:(xyA),(xyA)\forall x,y\in A:(x\lor y \in A),(x\land y\in A)
2 Asociatividad x,y,zA:x(yz)=(xy)zx,y,zA:x(yz)=(xy)z\forall x,y,z\in A:x\lor (y\lor z) = (x\lor y)\lor z\\\forall x,y,z\in A: x\land (y\land z) = (x\land y)\land z
3 Conmutatividad x,yA:xy=yxx,yA:xy=yx\forall x,y\in A: x\lor y = y\lor x\\\forall x,y\in A: x\land y = y\land x
4 Idempotencia xA:xx=xxA:xx=x\forall x\in A:x\lor x = x\\\forall x\in A:x\land x = x
5 Absorcion x,yA:x(xy)=xx,yA:x(xy)=x\forall x,y\in A: x\lor (x\land y) = x\\\forall x,y\in A: x\land (x\lor y) = x

Red Algebraica

Sea un conjunto A,y dos operaciones binarias y \text{Sea un conjunto }A\neq \varnothing,\\\text{y dos operaciones binarias} * \text{ y } *^\prime

(A;;) es Red Algebraica     y  son {CerradasAsociativasConmutativasIdempotentesy cumple con absorcion(A;*;*^\prime) \text{ es Red Algebraica} \iff * \text{ y } *^\prime \text{ son } \begin{cases} \text{Cerradas}\\ \text{Asociativas}\\ \text{Conmutativas}\\ \text{Idempotentes}\\ \text{y cumple con absorcion} \end{cases}

Toda red ordenada se puede expresar como red algebraica. Y toda red Algebraica se puede expresar como red ordenada.

Pasaje Datos Requerimientos
Ordenada \to Algebraica La relacion de \\ Orden Las operaciones \lor e :ab=supremo(a,b)ab=infimo(a,b)\land:\\ a\lor b = \text{supremo}(a,b) \\ a\land b = \text{infimo}(a,b)
Algebraica \to Ordenada Las operaciones \\ binarias \lor e \land La relacion de orden: abab=aabab=b\\a\preceq b \Leftrightarrow a\land b = a\\ a\preceq b \Leftrightarrow a\lor b = b

Complemento de un elemento

Sea (A;) una red con primer elemeto 0Ay ultimo elemento 1A\text{Sea }(A;\preceq) \text{ una red con primer elemeto } 0_A \text{y ultimo elemento } 1_A

Sea aA. Se define complemento de a\text{Sea } a\in A. \text{ Se define complemento de } a (a) si{aa=0Aaa=1A(\overline{a}) \text{ si}\begin{cases} a\land\overline{a}=0_A\\ a\lor\overline{a}=1_A \end{cases}

Red complementada

Una red es complementada    cada elemento tiene al menos un complemento\text{Una red es complementada} \iff \text{cada elemento tiene al menos un complemento}

Distributividad

Sea (A;;) una red, diremos que la red es distributiva sii:\text{Sea }(A;\lor;\land)\text{ una red, diremos que la red es distributiva sii:}

a,b,cA:a(bc)=(ab)(ac)a,b,cA:a(bc)=(ab)(ac) \forall a,b,c \in A:a\lor (b\land c) = (a\lor b)\land (a\lor c) \\ \forall a,b,c \in A:a\land (b\lor c) = (a\land b)\lor (a\land c)

Algebra de Boole

Un algebera de boole es una red distributiva y complementada

Sea (B;;)(B;\lor;\land) diremos que es Algebra de Boole sii:

Propiedades

En toda Algebra de Boole (B;;)(B;\lor;\land) se cummple:

  1. Todos los elementos 0B0_B y 1B1_B son unicos.
  2. Todo elemento tiene unico complemento.
  3. Todo elemento es idempotente: aB:a=aaa=a\forall a\in B: a=a\quad a\land a =a
  4. Los elementos neutros se complementan mutuamente: 1B=0B0B=1B\overline{1_B}=0_B\quad\overline{0_B}=1_B
  5. Todo elemento neutro es involutivo aB:a=a\forall a\in B:\overline{\overline{a}}=a
  6. El elemento neutro para \land es el 1B1_B y es absorbente para \lor.
  7. El elemento neutro para \lor es el 0B0_B y es absorbente para \land.
  8. Se cumple la absorcion: a,bB:a(ab)=a\forall a,b \in B: a\lor( a\land b)= a y a(ab)=aa\land (a\lor b) = a
  9. Se cumple la propiedad asociativa de \lor e \land. a,bB:a(bc)=(ab)c\forall a,b \in B: a\lor (b\lor c) = (a\lor b) \lor c y a,bB:a(bc)=(ab)c\forall a,b \in B: a\land (b\land c) = (a\land b) \land c
  10. Leyes de Demorgan: a,bB:ab=abab=ab\forall a,b \in B: \overline{a\lor b} = \overline{a} \land \overline{b}\quad \overline{a\land b} = \overline{a} \lor \overline{b}

Sub Algebra de Boole

Sea (B;) un Algebra de Boole, y AB,A es subalgebra de B(A,/A)\text{Sea } (B;\preceq) \text{ un Algebra de Boole, y }\varnothing\neq A\sube B, A\text{ es subalgebra de } B \Leftrightarrow (A,\preceq_{/A}) es algebra de boole, y se mantienen los mismos supremos e infimos y elementos neutros.

Homomorfismos de Algebras de Boole:

Sean (A,,)(A,\lor,\land) y (B,,)(B,\lor^\prime,\land^\prime) dos Algebras de Boole, con primeros elementos 0A0_A y 0B0_B respectivamente, y ultimos elementos 1A1_A y 1B1_B

Un homomorfismo de Algebras de Boole es una funcion f:AB/f:A \to B/

Si la funcion es bitectiva, se denomina isomorfismo. Para ello es necesario que los conjuntos tengan cardinales iguales. "Dos redes son isomorfas cuando tienen la misma forma aunque distintos elementos".

Funciones Boolenas

BnB siendo (B;;) Algebra de BooleB^n\to B \text{ siendo } (B;\lor;\land) \text{ Algebra de Boole}

son las tablas de la verdad.

Circuitos combinacionales

son la representacion de una funcion booleana.

Minitermino

Es un termino en el que intervienen todas las variables o sus complementarios multiplicadas entre si.

Forma Normal Disyuntiva (FND)

Se dice que una funcion booleana esta expresada en forma normal disyuntiva (FND) cuando esta expresada como suma de mini terminos.

Maxitermino

Es un factor en el que intervienen todas las variables o sus complementos Sumadas entre si

Forma Normal Disyuntiva (FNC)

Se dice que una funcion booleana esta expresada en forma normal conjuntiva (FNC) cuando esta expresada como producto de maxi terminos.

Conjuntos Funcionalmente Completos

  1. {AND, OR, NOT}
  2. {AND,NOT}
    1. x+y=xyx+y=\overline{\overline{x}\cdot\overline{y}}
  3. {OR, NOT}
    1. xy=x+yx\cdot y=\overline{\overline{x}+\overline{y}}
  4. {NAND}
    1. x=xx\overline{x} = \overline{x\cdot x}
    2. xy=xyxyx\cdot y = \overline{\overline{x\cdot y}\cdot \overline{x\cdot y}}
    3. x+y=xxyyx+y = \overline{\overline{x\cdot x}\cdot \overline{y\cdot y}}
  5. {NOR}
    1. x=x+x\overline{x} = \overline{x+x}

Relaciones de Recurrencia

f:NR/nN:f(n)=anf:\N\to \R/\forall n\in \N:f(n)=a_n

ana_n sera entonces el termino generico o general.

Recursion

Una definicion es recursiva si hace referencia a si misma.

En las sucesiones se denota una expresion recursiva cuando, a la hora de calcular un ana_n necesitamos conocer un an+1a_{n+1}, osea un ana_n anterior o posterior, impidiendo hacer le calculo directo.

Distinto seria el caso en el que para determinar un ana_n basta con reemmplazar el valor de nn en la expresion que nos dieron.

Entonces resolver una relacion de recurrencia es expresar nuesrta ecaucion recursiva en una no recursiva.

Expresion Recursiva    Expresion NO Recursivaan=2an1(a1=4)an=2n+1\begin{aligned} \text{Expresion Recursiva} \iff& \text{Expresion NO Recursiva} \\ a_n = 2\cdot a_{n-1} {\scriptstyle(a_1=4)} \qquad& a_n=2^{n+1}\end{aligned}

Clasificacion de Relaciones de Recurrencia

  1. Orden: Es la mayor diferencia entre los subindices de los elementos de la sucesion. Cuantos terminos anteriores hay que conocer para obtener uno particular.
  2. Grado: Es el mayor exponente al que estan elevados los elementos de la sucesion que figuran en la relacion de recurrencia.
  3. Ecaucion Homogenea: Al igual que las ecuaciones algebraicas, las ecuaciones homogeneas son las que no tienen terminos independientes. Es la ecuasion solamente con los ana_n
  4. Coeficientes Constantes: en estas ecuaciones ninguno de los coeficientes de los elementos de la sucesion dependen de n. Por el contrario si alguno depende de n, se dice que la ecuacion tiene coeficientes variables.

Tipos de Relaciones de Recurrencia:

Lineales de orden 1, Homogeneas

Formula:

an=kan1 siendo k una cte real no nulaa_n=ka_{n-1} \quad\small \text{ siendo } k \small\text{ una cte real no nula}

Datos:

Forma no recursiva:

an=kan1an=kna0a_n= ka_{n-1} \rArr a_n=k^n a_0

Aclaraciones: En estos casos se despeja el ana_n de mayor indice.

Lineales de orden 2, Homogeneas

Formula:

cnan+cn1an1+cn2an2=0 siendo cn,cn1,cn2 ctes reales no nulasc_n a_n + c_{n-1} a_{n-1} + c_{n-2} a_{n-2} = 0 \quad\small \text{ siendo } c_n, c_{n-1}, c_{n-2} \small\text{ ctes reales no nulas}

Suponiendo que an=xna_n =x^n, es una solucion valida para la ecuacion:

Reemplazo an por xncnxn+cn1xn1+cn2xn2Saco factor comun del xn de menor gradoxn2(cnx2+cn1x+cn2)=0Como xn2 no puede ser 0, igualo a 0 el otro productocnx2+cn1x+cn2=0Esto es una ecuacion cuadratica, se la llama caracteristicar1,r2{reales y distintas: an=k1r1n+k2r2nreales e iguales: an=k1r1n+k2nr1ncomplejasLuego NOS DEBEN DAR DOS DATOS para obtener el k1 y k2 se plantea un sistemas de ecuaciones con esos dos datos \text{Reemplazo } a_n \text{ por } x^n \\ c_n x^n + c_{n-1} x^{n-1} + c_{n-2} x^{n-2} \\ \text{Saco factor comun del } x^n \text{ de menor grado} \\ x^{n-2}\cdot (c_n x^2 + c_{n-1} x + c_{n-2}) = 0 \\ \text{Como } x^{n-2} \text{ no puede ser 0, igualo a 0 el otro producto} \\ c_n x^2 + c_{n-1} x + c_{n-2} = 0 \\ \text{Esto es una ecuacion cuadratica, se la llama caracteristica} \\ r_1,r_2\begin{cases} \text{reales y distintas: } a_n = k_1 r_1^n + k_2 r_2^n\\ \text{reales e iguales: }a_n = k_1 r_1^n + k_2 n r_1^n\\ \text{complejas} \end{cases} \\ \text{Luego NOS DEBEN DAR DOS DATOS para obtener el k1 y k2 } \\ \text{se plantea un sistemas de ecuaciones con esos dos datos}

Lineales de orden 1, No Homogeneas

Formula:

cnan+cn1an1=f(n)an=anH+anPc_n a_n + c_{n-1} a_{n-1} = f(n) \quad \rArr \quad a_n = a_{nH} + a_{nP}

anH:a_{nH}: Solucion general de la ecuacion homogenea.

anP:a_{nP}: Solucion particular de la ecuacion dada.

Aclaraciones: La solucion del homogeneo es la general, sin tener en cuenta condiciones iniciales. En cambio la solucion particular se plantea como una funcion del mismo tipo que f(n)f(n). Si no, se va multiplicando por n sucesivamente hasta hallarla. Por ultimo se plantean condiciones iniciales para despejar las constantes.

f(n)f(n) Solucion Particular Provable
K(cte)K\small (cte) B(cte)B \small (cte)
KnKn Bn+CBn + C
Kn2Kn^2 Bn2+Cn+DBn^2 + Cn + D
KntKn^t Polinomio completo de grado tt
KanKa_n BanBa_n

ACLARACION: Si aparece un termino como KtnKt^n la solucion particular sera BtnBt^n

Si no funka la solucion provable hay que multiplicarla por n hasta que funke, osea se amuenta el grado del polinomio.

estas soluciones provables se reemplazan en la ecuacion y luego esta ecuacion se resuelve como las anteriores.

  1. Se determina una ecuacion Homogenea asociada (sin las cte).
    1. Se obtiene una solucion para la ecuacion homogenea asociada. Esta tendra una constante que despues debemos despejar.
  2. Se elige la solucion particular dependiendo del caso
    1. En la ecuacion original, se reemplaza cada ana_{n} por la solucion particular (que no conocemos sus ctes).
    2. Despejamos la solucion particular. Obtenemos anPa_{nP}
  3. La ecuacion no recursiva sera an=anH+anPa_n = a_{nH} + a_{nP}
    1. Ahora si podemos despejar la constante de la solucion homogenea asociada.

Datos:

Lineales de orden 1, No Homogeneas

Formula:

cnan+cn1an1+cn2an2=f(n)an=anH+anPc_n a_n + c_{n-1} a_{n-1} + c_{n-2} a_{n-2} = f(n) \quad \rArr \quad a_n = a_{nH} + a_{nP}

Congruencias en Z\Z

Congruencia modulo n

En Z:aRbab(n)nab\text{En }\Z: \quad aRb \Leftrightarrow a\equiv b(n)\Leftrightarrow n\vert a-b

x,yZ:Si xa(n)yb(n)x+ya+b(n)\forall x,y\in \Z : \text{Si } x\in\overline{a}(n)\land y\in\overline{b}(n) \rArr x+y \in \overline{a+b}(n)

x,yZ:Si xa(n)yb(n)xyab(n)\forall x,y\in \Z : \text{Si } x\in\overline{a}(n)\land y\in\overline{b}(n) \rArr x\cdot y \in \overline{a\cdot b}(n)

Funcion de Euler

ϕ(n)={xN/xnmcd(x,n)=1}\phi (n) = \lvert \{x\in\N / x\leq n\land \text{mcd}(x,n)=1 \} \rvert

Osea me devuelve cuantos numeros coprimos hay hasta el numero nn

  1. Si pp es un numero primo, entonces: ϕ(p)=p1\phi(p)=p-1
  2. Si n es un numero natural y p es numero primo:

ϕ(pn)=pn(11p)ϕ(pn)=pn1(p1)\phi(p^n) = p^n\cdot \left(1-\frac{1}{p}\right) \quad \phi(p^n) =p^{n-1}(p-1)

  1. Si n,mN y mcd(n,m)=1:ϕ(nm)=ϕ(n)ϕ(m)n,m\in\N \text{ y mcd}(n,m)=1:\phi(n\cdot m)=\phi(n)\cdot \phi(m)
  2. ϕ(n)=n(11p1)(11p2)(11pr)\phi(n)= n\cdot \left(1-\frac{1}{p_1}\right)\cdot \left(1-\frac{1}{p_2}\right)\cdot\cdots\cdot\cdot \left(1-\frac{1}{p_r}\right)

Teorema de Fermat

Si p es primomcd(a,p)=1ap11(p)\text{Si }p\text{ es primo} \land \text{mcd}(a,p)= 1\rArr a^{p-1}\equiv 1(p)

Este teorema se usa para ir simplificando los exponentes para verificar si el resto de una division cae en una clase

Teorema de Euler-Fermat

Si mcd (a,n)=1aϕ(n)1(n)\text{Si mcd } (a,n)=1 \rArr a^{\phi(n)}\equiv 1(n)

Ecuaciones Lineales de Congruencia

axb(n)a\cdot x\equiv b(n)

Sea axb(n).Si mcd (a,n)=1 entonces hay solucion.\text{Sea } a\cdot x\equiv b(n).\qquad \text{Si mcd }(a,n)=1 \text{ entonces hay solucion.}

x=aϕ(n)1bx=a^{\phi(n)-1}\cdot b

axb(n) tiene solucion mcd(a,n)b y la cantidad de soluciones es mcd(a,n)a\cdot x \equiv b(n) {\small\text{ tiene solucion }} \Leftrightarrow \text{mcd}(a,n)\vert b\quad {\small\text{ y la cantidad de soluciones es }} \text{mcd} (a,n)

Esto sirve tambien para simplificar las ecuaciones, se puede dividir termino a termino por la cantidad de soluciones, luego resolver la ecuacion, y finalmente al resultado de la eq simplificada se le suma el modulo simplificado la cantidad de soluciones que hallamos obtenido.

Si:acbc(n)mcd(c,n)=1Entonces ab(n)\text{Si}: a\cdot c\equiv b\cdot c(n)\land \text{mcd}(c,n)=1 \\\text{Entonces }a\equiv b(n)

Grupos

OP cerradas

\ast es una operacion binaria cerrada en AA sii: x,yA:xyA\forall x,y\in A: x\ast y\in A

Sea un conjunto A:A×AAA\neq \varnothing\\\ast:A\times A\to A es operacion cerrada en A \lrArr\ast es funcion.

Tambie se llama ley de cierre o lci

Propiedades y elementos notables de una OP cerrada

Sea AA\neq \varnothing y * es una operacion cerrada definida en AA

Operaciones combinada

Se tiene que verificar si:

el neutro siempre es idempotente

Grupos

  1. Si * es op. cerrada (A;)\rArr (A;*) es Grupoide
  2. Si ademas * es asociativa (A;)\rArr (A;*) es Semigrupo
  3. Si ademas * tiene neutro (A;)\rArr (A;*) es Monoide
  4. Si ademas * tiene simetrico (A;)\rArr (A;*) es Grupo

Propiedades de grupos.

  1. el elemento neutro es unioco
  2. el eutro es su propio simetrico e=ee = e\prime
  3. propiedad involutiva del simetrico aA:(a)=a\forall a\in A: (a\prime)^\prime= a
  4. el simetrico de un elemetno es unico
  5. a,bA:(ab)=ab\forall a,b\in A: (a*b)^\prime= a^\prime*b^\prime
  6. las ecuaciones lineales tienen solucion unica
  7. el unico elementoidempotente es el elemento neutro
  8. a,b,A:a=bb=a\forall a,b,\in A: a^\prime=b \rArr b^\prime=a

Dem prop 1: elemento neutro es unico

Suponiendo que hay dos elementos neutros e1e_1 y e2e_2

xA:  xe1=xe2e1=e2xA:  xe2=xe2e1=e1e1=e2 \forall x\in A: \;x*e_1 = x \\ e_2*e_1=e_2 \\ \forall x\in A: \;x*e_2 = x \\ e_2*e_1=**e_1** \\ e_1=e_2

Dem prop 2: el neutro es su propio simetrico

xAxe=ex=xee=ee=eaa=aa=ee=e \forall x\in A \rArr x*e = e*x=x \\ e*e = e*e = e \land a* a^\prime = a^\prime *a = e \\ e^\prime = e

Grafos

Un Grafo es una terna G=(V;A;ϕ)\quad G=(V;A;\phi)\\ Donde:

Representacion matricial de Grafos

Caminos y Ciclos en Grafos

Caminio y Ciclo de Euler

Un grafo tiene camino euleriano sii es conexo y en todos los vertices tienen grado par, o a lo sumo dos grado impar.

Un grafo tiene ciclo euleriano sii es conexo y todos los vertices tienen grado par

Caminio y Ciclo de Hamilton

Grafos Regulares

Grafos Completos

Grafo Bipartito

Grafo Bipartito Completo

Subgrafo

Grafos Conexos

Desconexion de grafos

Grafos Planos

Un grafo es plano sii no contiene ningun subgrafoisomorfo al K3,3K_{3,3} o al K5K_5

Isomorfismos

Para que dos grafos sean isomorfos sus matrices de incidencia deben ser isomorfas.

Digrafos

Un Digrafo es una terna G=(V;A;δ)\quad G=(V;A;\delta)\\ Donde:

Camino Simple y Camino Elemental en Digrafo

Funcion grado en un digrafo

Propiedades

Representacion Matricial de Digrafos.

Grafo asociado a un Digrafo

Se simplifica las direccion de las aristas, de haber aristas paralelas si reemplaza por una sola arista

Conexidad en Digrafos

Camino de Euler y Hamilton en digrafos

Condicion necesaria y suficiente para que exista ciclo de Euler en un digrafo:

vV:g+(v)=g(v)\forall v\in V:g^+(v)=g^-(v)

Isomorfismos en Digrafos

es la misma wea que en los grafos solo que hay que tener cuidado con la direccionalidad de las aristas

Arboles

Un arbol es un grafo conexo sin ciclos.

Propiedades

  1. Al agregar una arista entre dos vertices de un arbol, deja de ser arbol
  2. Todas las aristas de un arbol son puentes.
  3. En todo arbol se cumple que V=A+1\lvert V\rvert = \lvert A\rvert+1

Bosques

Un bosque es un grafo no conexo en el cual cada una de sus componentes es un arbol.

Arboles Dirigidos

Un digrafo simple es un arbol dirigido si su grafo asociado es un arbol.

Grafo Dirigido con raiz: es un arbol en el cual el grado entrante (positivo) de cada vertice es igual a 1, salvo un unico verticve con grado positivo igual a cero llamado raiz.

Definiciones:

Otras Definiciones:

Arbol nn-ario

Recorridos de Arboles

Rrcorrer un arbol es una forma de nombrar todos los vertices segun un orden determinado.

Representacion de expresiones algebraicas

se puede representar una suma como un arbol, y asi con el resto de operaciones.

Lenguajes

Alfabeto

Conjunto finito no vacio, sin elementos que se obtengan por yuxtaposicion (poner dos letras consecutivas).

Se simboliza con la letra V o con \sum

Clausura de Kleene de un Alfabeto

V=V0V1V2VnV^*= V^0\cup V^1\cup V^2\cup\cdots V^n\\ ViV^i: conjunto de palabras de longitud ii formadas con las letras del alfabeto VV\\ Entonces VV^* sera el conjunto de todas las palabras, de cualquier longitud, que se puede escribir con letras del alfabeto.

Concatenacion de palabras.

Literalmente concatenar palabras, se simboliza como w3=w1w2w_3=w_1\cdot w_2 siendo w1,w2,w3w_1,w_2,w_3 palabras.

Inversion o trasposicion: es la palabra que se obtiene al escribir dicha palabra de "atras hacia adelante" se simboliza wRw^R

Palindromo

Sea ww una palabra V,w\in V^*,w es palindromo     w=wR\iff w=w^R

Potencai de una palabra

Sea wVw\in V^* se define:

{w0=λw1=wcon nN0wn=wwn1\begin{cases} w^0=\lambda\\ w^1 = w & \text{con }n\in\N_0\\ w^n = w\cdot w^{n-1} \end{cases}

Lenguaje

Sea LL un conjunto y VV un alfabeto. LL es un lenguaje     LV\iff L \sube V^*

Concatencaion de Lenguajes

L=L1L2={xy/xL1yL2}L = L_1\cdot L_2 = \{xy/x\in L_1 \land y\in L_2\}

  1. L1L2L1L2\lvert L_1\cdot L_2\rvert \leq \lvert L_1\rvert \cdot \lvert L_2\rvert
  2. (P(V);)(P(V^*);\bullet) semigrupo con neutro L=ΛL=\Lambda
  3. L1L2L2L1L_1\cdot L_2 \neq L_2\cdot L_1
  4. L=L=\varnothing es elemento absorbente de la concatenacion.
  5. Si L1L2L_1\sub L_2 y L3L4L_3\sub L_4 entonces L1L3L2L4L_1\cdot L_3 \sub L_2\cdot L_4

Lenguaje inverso reflejo o traspuesto:

LR={wR/wL}L^R=\{w^R/w\in L\}, son todas las palabras del lenguaje reflejadas.

Potencia de un Lenguaje

{L0={λ}L1=Lcon nN0Ln=LLn1\begin{cases} L^0 = \{\lambda\} \\ L^1 = L & \text{con }n\in\N_0\\ L^n= L\cdot L^{n-1} \end{cases}

Clausura de Kleene de un Lenguaje

L=n=0Ln=L0L1L2LnL^*= \bigcup_{n=0}^\infin L^n= L^0\cup L^1\cup L^2\cup \cdots \cup L^n\cup \cdots

Clausura Positiva de un Lenguaje

L+=n=1Ln=L1L2LnL^+= \bigcup_{n=1}^\infin L^n= L^1\cup L^2\cup \cdots \cup L^n\cup \cdots

Complemento de un Lenguaje

L=VL\overline{L}=V^*-L

Gramatica

G=(Vn;Vt;P;S)G=(V_n;V_t;P;S)\\ Vn:V_n: Vocabulario o alfabeto de no terminales.\\ Vt:V_t: Vocabulario o alfabeto de Terminales.\\ P:P: Producciones.\\ S:S: Simbolo o variable inicial.

Aclaraciones:

Gramaticas equivalentes

Son las que generan el mismo lenguaje.

Tipos de Gramaticas (Jerarquia de Chomsky)

Tipo Nombre Producciones
0 Irrestricta Cualquier forma
1 Sensible al Contexto aXbaYbaXb\to aYb donde a,b,YV  XVn\\ a,b,Y\in V^* \;X\in V_n
2 Independiente del Contexto XYX\to Y donde XVnX\in V_n
3 Regular XYX\to Y donde XVnYX\in V_n \\ Y puede ser Vt,tVt,t o λ\lambda (derecha) Y\\ Y puede ser tV,ttV,t o λ\lambda (izquierda)

Un lenguaje puede estar generado por distintas gramaticas de distinto tipo para un mismo lenguaje, pero el tipo del lengua sera el de la gramatica de mayor tipo.

digraph g{ rankdir=LR; g [label=gramatica, shape= rectangle] l [label=lenguaje, shape= rectangle] g -> l [label=Unico] l -> g [label=Muchos] }

Expresiones Regulares

Una ER es una secuencia de elementos que verifica:+

Automatas Finitos

Maquinas de estados finitos

Lenguaje Tipo Maquina que lo Reconoce
0 Mauina de Turing
1 Automata linealmente Acotado
2 Automata de Pila (Push Down)
3 Automata Finito

Automata Finito

A=(Q,V,λ,q0,F)A=(Q,V,\lambda,q_0,F)\\ Q:Q: Conjunto finito de estados V:V: vocabulario o alfabeto de enrtada λ:\lambda: Q×VQQ\times V\to Q. Funcion de transision q0:q_0: Estado Inicial F:F: Conjunto de estados finales FF\neq \varnothing y FQF\sub Q

Tabla de Transicion

\, xx yy
q0q_0 q0,q1q_0,q_1 q1q_1
q1q_1 q2q_2
q2q_2 q1q_1

Clasificacion de los Automatas Finitos

Automatasfinitos{A.F.D: DeterministicoA.F.N: No Deterministico\text{Automatas\\finitos}\begin{cases} \text{A.F.D: Deterministico}\\ \text{A.F.N: No Deterministico} \end{cases}

graph TB; Expresion_Regular--->Automata_Finito; Automata_Finito--->Expresion_Regular; Expresion_Regular--->Gramatica_Regular; Automata_Finito--->Gramatica_Regular; Gramatica_Regular--->Automata_Finito; Gramatica_Regular--->Expresion_Regular;

Digrafo de AF a Expresion Regular

  1. p=aqp = a\cdot q
digraph regla1 { rankdir = LR; p -> q [label=a]; }
  1. p=aq+brp= a\cdot q + b\cdot r
digraph regla2 { rankdir = LR; p -> q [label=a]; p -> r [label=b]; }
  1. p=app=ap= a\cdot p \rArr p= a^*
digraph regla3 { rankdir = LR; p -> p [label=a]; }
  1. p=ap+bqp=a(bq)p = a\cdot p + b\cdot q \rArr p= a^*\cdot(b\cdot q)
digraph regla4 { rankdir = LR; p -> p [label=a]; p -> q [label=b]; }
  1. p=λp=\lambda
digraph regla4 { rankdir = LR; p[shape=doublecircle]; }